package chapter3.four;

import chapter3.BiNode;

public class Test {

	
	private static int maxSum=Integer.MIN_VALUE;
	/**
	 * 求最大子树
	 * @param root 根节点
	 * @param maxRoot 最大子树的根节点
	 * @return 以root为根节点子树所有节点的和
	 */
	public static int findMaxSubTree(BiNode root,BiNode maxRoot) {
		if(root==null) {
			return 0;
		}
		//求root左子树所有节点的和
		int lMax = findMaxSubTree(root.lChild, maxRoot);
		//求root右子树所有节点的和
		int rMax = findMaxSubTree(root.rChild, maxRoot);
		
		int sum=lMax+rMax+root.data;
		
		//以root为根的子树的和大于前面求出的最大值
		if(sum>maxSum) {
			maxSum=sum;
			maxRoot.data=root.data;
		}
		//返回以root为根节点的子树的所有节点的和
		return sum;
	}
	
	/**
	 * 构造二叉树
	 * @return 返回新构造的二叉树的根节点
	 */
	public static BiNode constructTree() {
		BiNode root=new BiNode();
		BiNode node1=new BiNode();
		BiNode node2=new BiNode();
		BiNode node3=new BiNode();
		BiNode node4=new BiNode();
		
		
		root.data=6;
		node1.data=3;
		node2.data=-7;
		node3.data=-1;
		node4.data=9;
		
		root.lChild=node1;
		root.rChild=node2;
		
		node1.lChild=node3;
		node1.rChild=node4;
		
		node2.lChild=node2.rChild= node3.rChild=node4.lChild=node4.rChild=null;
		
		return root;
	}
	
	public static void main(String[] args) {
		BiNode root = constructTree();
		
		BiNode maxRoot = new BiNode();//最大子树的根节点
		
		findMaxSubTree(root, maxRoot);
		
		System.out.println("最大子树和为："+maxSum);
		System.out.println("对应子树的根节点为："+maxRoot.data);
	}
}
